In the newly developed coding standard High Efficiency Video Coding (HEVC) system, the fixed-size macroblock (MB) of H.264/AVC is replaced by a flexible block, named coding unit (CU). Pixels in the CU share coding parameters to improve coding efficiency. Partition of a picture begins with a largest CU (LCU), also referred as coded tree unit (CTU), and each LCU is adaptively split into leaf CUs. In addition to the concept of coding unit, the concept of prediction unit (PU) is also introduced in HEVC. Once the splitting of CU hierarchical tree is done, each leaf CU is further split into one or more prediction units (PUs) according to prediction type and PU partition.
Along with the HEVC standard development, Screen Content Coding Extension (SCC) of HEVC standard is being developed under JCTVC. Due to specific characteristics of screen contents, coding tools have been developed and demonstrate significant gains in coding efficiency. Among them, the palette coding (a.k.a. major color based coding) techniques represent a block of pixels using indices pointing to a palette of major colors, and encode the major colors, together with the coded palette index map representing the block. While the total number of possible color combinations is huge, the number of colors in a local area of a picture is usually very limited for typical screen contents. Most objects in screen contents have relatively uniform colors and are separated by sharp edges. Therefore, the palette coding techniques used in palette mode become very effective for coding screen contents including web page browsing, Word document editing, PowerPoint files, or screen captures with mixtures of multiple applications.
The coding process in palette mode consists of two steps: the palette table coding process and the palette index map coding process. The palette table coding comprises locating a number of major colors from a current block and mapping the major colors to palette indices. Other colors in the current block are defined as escape colors, which are coded not using the palette index but the quantization of the pixel values. The palette table containing the palette indices conducts predictive coding by referring to palette colors from previous palette-coded blocks. Predictive coding utilizes a palette predictor table and palette stuffing to reconstruct the palette table.
The palette predictor table is formed to keep track of the major colors used by the palette coded blocks. When a current block is selected to be coded in palette mode, colors in the palette predictor table predict the palette of the current block by signaling a stream of palette reuse flags. FIG. 1 illustrates the palette reconstructing process specified in SCC Draft Text 3. A palette of the current block 12 is predicted from a palette predictor table 14 according to a palette reuse flag array 16. The palette reuse flag array 16 indicates the positions of entries in the palette predictor table 14 that are reused by the current block palette 12. In FIG. 1, palette reuse flags in the palette reuse flag array 16 are {1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0}, indicating the first, third, fourth, eighth, and thirteenth entries in the palette predictor table 14 are reused colors 122 for the current block palette 12. The palette reuse flags are coded by run-length coding, so the number of zeros, which is the run value, between two ones are coded by a syntax element palette_predictor_run. In a decoder, a palette reuse flag is set to 1 when a corresponding palette_predictor_run is parsed and decoded, and the color in the palette predictor table 14 indicated by the palette reuse flag is included in the palette of the current block 12. After all the palette_predictor_run are decoded, all the corresponding palette reuse flags are set and all the reused colors 122 for the current block palette 12 are found. Beside the reused colors 122 derived from the palette predictor table 14, the current block palette 12 may also contain new colors 124. The new colors 124 are signaled directly in the bitstream. A syntax element num_signalled_palette_entries is signaled to indicate the number of new colors 124 in the current block palette 12.
The palette index map coding process encodes information including palette index scanning orientation and the palette index map. The palette index scanning orientation is coded using a transpose flag palette_transpose_flag. The palette index map refers to the block expressed by replacing the pixel values of the current block with palette indices. Several palette run types include COPY_INDEX mode, COPY_ABOVE mode, and ESCAPE mode. In the COPY_INDEX mode, run-length coding is conducted for the palette index value, and the palette run type, palette index, and run-length are coded. In the COPY_ABOVE mode, which copies the palette index of the above row, the palette run type and run-length are coded. In the ESCAPE mode, which uses the pixel value as it is, the palette run type and the quantized pixel value are coded.
Pixels in the current block are coded by the palette index map in a predetermined scanning order according to the transpose flag. For each group of one or more pixels, the palette run type is determined to indicate which mode is being used. When a group of pixels is coded in the COPY_INDEX mode, a palette index is first decoded followed by palette run representing the run-length. The run-length palette run indicates a total number of samples coded using the COPY_INDEX mode. When a group of pixels is coded in the COPY_ABOVE mode, a run-length copy_run is decoded to indicate that for the following pixels including the current one, the palette index is the same as the corresponding palette index in the row above.
In the development of SCC standard, a modification of the palette index map coding process includes inserting a last run flag to signal whether the current run is the last run in the palette index map for the processed block. This signaling method is called Run-to-the-end signaling and is particularly useful when the last run is long. When the last run flag is 1, the remainder of the processed block uses the same mode, either the COPY_INDEX mode or the COPY_ABOVE mode, so signaling the actual number of elements included in the run is no longer needed.
Another modification of the palette index map coding process includes grouping palette indices at front and not-signaling-the-last-run. All the palette indices in a current block are grouped together and signaled before syntax elements for the palette run type and the palette run length. The not-signaling-the-last-run method signals the number of palette indices and a flag used to indicate the last palette run type is the COPY_ABOVE mode or the COPY_INDEX mode. The decoder derives the last run from the number of palette indices and the last palette run type flag. The run length of the last run can be derived to reach the end of the current block, so there is no need to signal the last run. Similar to the above Run-to-the-end signaling method, this not-signaling-the-last-run signaling modification is particularly efficient when coding a long last run.
When signaling all the palette indices before signaling other syntax elements, these palette indices have to be stored for reconstructing the palette index map. The palette indices are stored in a temporary buffer at least until the palette run type and palette run length are parsed. An additional temporary buffer, in addition to the buffer for storing the palette index map, is required, unless reusing the palette index map buffer and inserting the palette index data into the end of the palette index map buffer. The order of palette index map syntax signaling in HEVC SCC test model SCM-4.0 becomes: Number of palette indices→Group of all palette indices→Last palette run type flag→{palette run type, run length} interleaved pairs→Group of all Escape values.